2014년도 운영체제 1학기 텀 프로젝트 1

<버디 메모리 구현>

버퍼 캐쉬의 정의
버디 메모리 할당(buddy memory allocation) 기술은 가능한 적당하게 메모리 요청을 만족하도록 메모리를 여러 부분으로 나누는 메모리 할당 알고리즘이다. 이 시스템은 메모리의 크기를 절반씩 분할을 하면서 가장 잘 맞는 크기의 메모리를 찾는다. 도널드 크누스(Donald Knuth)에 의하면, 버디 시스템은 1963년에 해리 마코위츠(Harry Markowitz, 1990년 노벨 경제학상 수상)가 고안한 것으로, 켄 놀튼(Kenneth C. Knowlton, 1965년 출판)[1]에서 처음으로 선보였다.

목적
메모리 관리기법중 하나인 버디메모리를 구현해봄으로써 커널이 어떻게 메모리를 관리하고 접근하는지 이해하고 숙지한다.

개요
버디 메모리 할당 기술은 2의 거듭제곱 값(예를 들면, [eqn: 2 ^{x}]. 여기서 x는 숫자)으로 메모리를 할당한다. 따라서 프로그래머는 x값의 상한선을 결정하거나 구할 수 있는 코드를 작성해야 한다. 예를 들면, 시스템이 2000K의 물리적인 메모리를 가지고 있다면, [eqn: 2 ^{20}](1024K)이 할당할 수 있는 가장 큰 블록이기 때문에 x값의 상한선은 20이 될 것이다. 이는 단일 청크에 물리적 메모리 전부를 할당하는 것이 불가능하기 때문이다. 남은 976K 메모리는 좀 더 작은 블록들로 할당이 되어야 한다. 상한선(앞으로는 상한선을 u 로 표기하겠음)을 결정한 뒤에는, 프로그래머는 할당될 수 있는 가장 작은 메모리 블록인 하한선을 결정해야 한다. 이 하한선은 저장하는데 발생되는 오버헤드를 최소화하고 비어있는 메모리 공간을 최소화하기 위해서 필요하다. 이 하한선이 없다면, 많은 프로그래머들은 1K나 2K 같은 작은 블록의 메모리를 요구할 것이고, 시스템은 할당되고 할당되지 않은 블록들을 기억하기 위해서 많은 공간을 낭비하게 될 것이다. 전형적으로 이 숫자(12 같은, 212 = 4K 블록에 할당된 메모리)는 공간의 낭비를 최소화할 수 있을 만큼 충분히 작은 적당한 숫자이고, 과도한 오버헤드를 피할 수 있을 만큼 충분히 큰 숫자이기도 하다.

예시(메모리 할당)

적당한 크기의 메모리 슬롯을 찾는다.(최소한 요청된 메모리와 동일하거나 큰 2k 블록)

적당한 크기의 메모리 슬롯이 발견되면, 프로그램에 할당한다.

적당한 크기의 메모리 슬롯이 발견되지 않으면, 적당한 메모리 슬롯을 만들기를 시도한다. 시스템은 아래의 일들을 시도한다.

요청된 메모리 크기보다 크게 절반씩 빈 메모리 슬롯을 자른다.

하한선에 도착하게 되면, 해당 메모리(하한선 크기의 메모리)를 할당한다.

다시 첫 번째 단계로 돌아간다.(적당한 크기의 메모리를 찾기 위해서)

적당한 메모리 슬롯이 발견될 때 까지, 이 과정을 반복한다.

예시(메모리 해제)

메모리 블록을 해제한다.

주변의 블록들을 살펴 본다 - 주변 블록들도 해제된 상태인가?

만약 그렇다면, 두 메모리 블록을 조합하고 다시 두 번째 단계로 돌아간다. 그리고 해제된 모든 메모리들이 상한선에 도달할 때까지 이 과정을 반복하거나, 해제되지 않은 주변 블록들을 마주칠 때까지 반복한다.

개발환경

Platform : Windows

Dev. Language : C/C++(MFC 사용 권장-Console도 무방함)

제출 마감 기한
10월 17일 (금) 23:59 까지

텀 프로젝트 구성 인원
개인 별

제출 방식
소스와 실행 파일, 문서 파일을 압축하여 “Term02_학번_이름”으로 메일(lecture@oslab.khu.ac.kr) 로 보냄